// 最长公共子序列 （可以不连续）
function lcs(str1, str2) {
  let m = str1.length;
  let n = str2.length;
  // 定义res[i][j] 表示以str1中第i个 str2中第j个字符结尾的最长公共子序列 （可以不连续）
  // 构造res的二维数组
  let res = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 这里数组中是以下标为0 开始
      if (str1[i - 1] == str2[j - 1]) {
        res[i][j] = res[i - 1][j - 1] + 1;
      } else {
        res[i][j] = Math.max(res[i - 1][j], res[i][j - 1]);
      }
    }
  }
  return res[m][n];
}
// 最长公共子串 必须连续
function lcsc(str1, str2) {
  let m = str1.length;
  let n = str2.length;
  let result = 0;
  let res = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 如果 str1[i-1]!=str2[j-1] 则 res[i][j]=0 代表以第i个字符和第j个字符结尾的最长公共子串的长度为0
      if (str1[i - 1] == str2[j - 1]) {
        res[i][j] = res[i - 1][j - 1] + 1;
        result = Math.max(result, res[i][j]);
      }
    }
  }
  return result;
}
let res = lcs("1234", "102304");
let res1 = lcsc("1234", "102304");
console.log(res); // 4 "1234"
console.log(res1); // 2 "23"
